COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00006 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source
.turn on "→"
CS206∂(30)FINAL EXAMINATION→SPRING 1977

	This examination is open book and notes.
Write LISP functions as follows except where something else is
requested.  Either notation may be used.

1. %2alt1 u%1 contains alternate elements of the list %2u%1 in the
same order as in %2u%1 ending with the last element of %2u%1.
Thus

	%2alt1%1 (A B) = (B),

	%2alt1%1 (A B C) = (A C),

and

	%2alt1%1 (A B C D) = (B D).

2. %2iscompact x%1, where %2x%1 is a list structure, is true if all
EQUAL substructures in %2x%1 are EQ.

3. %2partitions n%1 is a list of the partitions of the integer %2n%1 into
sums of smaller integers.  Thus
%2partitions_1_=_((1)),
partitions_2_=_((2)_(1_1)),
%2partitions 3 = ((3)_(2_1)_(1_1_1)), and
%2partitions_4_= ((4) (3 1) (2 2) (2 1 1) (1 1 1 1))%1.

4. Define

	%2length u ← qif qn u qthen 0 qelse 1 + length qd u%1,

and as usual

	%2u*v ← qif qn u qthen v qelse qa u . [qd u * v]%1.

Prove that

	%2∀u v.(length[u*v] = length u + length v)%1.

In the proof you may use any facts you like about the properties of addition,
but you must state what facts you are using.

5. Let %2e%1 be a LISP expression formed from numbers and atoms using
PLUS and TIMES to represent addition and multiplication.  %2polyprint_e%1
is a list of the characters occurring in a printout of %2e%1 in
algebraic notation containing no unnecessary parentheses.  Thus

	%2polyprint%1 (TIMES (PLUS X (TIMES U V W)) X Z) =
(LP X PLUS U V W RP X Z)

which corresponds to the algebraic expression (X + UVW)XZ


6. What code will LCOM4 generate from
(DEFUN FF (X) (COND ((ATOM X) X) (T (FF (CAR X)))))?